/**
 * 二叉树的遍历
 *
 *      A
 *    /   \
 *   B     C
 *  / \   / \
 * D   E F   G
 *
 * 1. 前序遍历(先跟次序遍历，根节点在遍历结果最前)
 * - 遍历顺序：根节点 -> 左子树 -> 右子树
 * - 结果为 ABDECFG
 *
 * 2. 中序遍历(中跟次序遍历，根节点在遍历结果中间)
 * - 遍历顺序：左子树 -> 根节点 -> 右子树
 * - 结果为 DBEAFCG
 *
 * 3. 后序遍历(后跟次序遍历，根节点在遍历结果最后)
 * - 遍历顺序：左子树 -> 右子树 -> 根节点
 * - 结果为 DEBFGCA
 */

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new TreeNode("A");
const b = new TreeNode("B");
const c = new TreeNode("C");
const d = new TreeNode("D");
const e = new TreeNode("E");
const f = new TreeNode("F");
const g = new TreeNode("G");
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;


/**
 * 前序遍历
 * @param root 根节点
 */
function prevSort(root) {
  if (root == null) return;
  console.log("▶『前序遍历』", root.val); // 输出当前节点
  prevSort(root.left); // 输出左子树
  prevSort(root.right); // 输出右子树
}

prevSort(a);

/**
 * 中序遍历
 * @param root 根节点
 */
function midSort(root) {
  if (root == null) return;
  midSort(root.left); // 输出左子树
  console.log("▶『中序遍历』", root.val); // 输出当前节点
  midSort(root.right); // 输出右子树
}

midSort(a);

/**
 * 后序遍历
 * @param root 根节点
 */
function afterSort(root) {
  if (root == null) return;
  afterSort(root.left); // 输出左子树
  afterSort(root.right); // 输出右子树
  console.log("▶『后序遍历』", root.val); // 输出当前节点
}

afterSort(a);
